<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Section 4.3.1: Compute the Chebyshev center of a polyhedron</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/cvxbook/Ch04_cvx_opt_probs/html/chebyshev_center.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Section 4.3.1: Compute the Chebyshev center of a polyhedron</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Boyd &amp; Vandenberghe "Convex Optimization"</span>
<span class="comment">% Jo&euml;lle Skaf - 08/16/05</span>
<span class="comment">%</span>
<span class="comment">% The goal is to find the largest Euclidean ball (i.e. its center and</span>
<span class="comment">% radius) that lies in a polyhedron described by linear inequalites in this</span>
<span class="comment">% fashion: P = {x : a_i'*x &lt;= b_i, i=1,...,m}</span>

<span class="comment">% Generate the data</span>
randn(<span class="string">'state'</span>,0);
n = 10; m = 2*n;
A = randn(m,n);
b = A*rand(n,1) + 2*rand(m,1);
norm_ai = sum(A.^2,2).^(.5);

<span class="comment">% Build and execute model</span>
fprintf(1,<span class="string">'Computing Chebyshev center...'</span>);
cvx_begin
    variable <span class="string">r(1)</span>
    variable <span class="string">x_c(n)</span>
    dual <span class="string">variable</span> <span class="string">y</span>
    maximize ( r )
    y: A*x_c + r*norm_ai &lt;= b;
cvx_end
fprintf(1,<span class="string">'Done! \n'</span>);

<span class="comment">% Display results</span>
fprintf(1,<span class="string">'The Chebyshev center coordinates are: \n'</span>);
disp(x_c);
fprintf(1,<span class="string">'The radius of the largest Euclidean ball is: \n'</span>);
disp(r);
</pre>
<a id="output"></a>
<pre class="codeoutput">
Computing Chebyshev center... 
Calling SDPT3: 20 variables, 11 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 11
 dim. of linear var  = 20
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
    NT      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|2.9e+02|8.9e+00|2.8e+03| 1.721824e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|0.971|1.000|8.4e+00|6.8e-02|8.5e+01| 5.569883e+00 -4.336238e+00| 0:0:00| chol  1  1 
 2|0.940|1.000|5.0e-01|6.8e-03|8.0e+00| 6.227339e-01 -3.291097e+00| 0:0:00| chol  1  1 
 3|0.776|0.715|1.1e-01|2.4e-03|2.7e+00| 4.213392e-01 -1.146735e+00| 0:0:00| chol  1  1 
 4|0.831|0.952|1.9e-02|1.8e-04|4.0e-01| 3.637727e-01  9.795053e-02| 0:0:00| chol  1  1 
 5|1.000|0.969|5.3e-09|3.8e-03|6.9e-02| 3.535620e-01  2.863755e-01| 0:0:00| chol  1  1 
 6|1.000|0.987|5.8e-09|5.1e-05|2.6e-02| 3.479517e-01  3.218399e-01| 0:0:00| chol  1  1 
 7|0.988|1.000|4.5e-10|7.0e-08|1.0e-02| 3.392570e-01  3.288598e-01| 0:0:00| chol  1  1 
 8|1.000|0.844|4.5e-10|1.7e-08|1.8e-03| 3.374285e-01  3.356581e-01| 0:0:00| chol  1  1 
 9|1.000|1.000|1.4e-10|7.7e-10|3.5e-04| 3.371978e-01  3.368475e-01| 0:0:00| chol  1  1 
10|0.987|0.985|1.8e-12|1.1e-10|5.0e-06| 3.370613e-01  3.370563e-01| 0:0:00| chol  1  1 
11|1.000|0.996|3.6e-13|1.5e-12|7.2e-08| 3.370594e-01  3.370594e-01| 0:0:00| chol  1  1 
12|1.000|0.997|6.9e-14|1.0e-12|8.9e-10| 3.370594e-01  3.370594e-01| 0:0:00|
  stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 12
 primal objective value =  3.37059399e-01
 dual   objective value =  3.37059398e-01
 gap := trace(XZ)       = 8.91e-10
 relative gap           = 5.32e-10
 actual relative gap    = 5.32e-10
 rel. primal infeas     = 6.87e-14
 rel. dual   infeas     = 1.00e-12
 norm(X), norm(y), norm(Z) = 1.5e-01, 7.7e+00, 2.4e+01
 norm(A), norm(b), norm(C) = 1.9e+01, 2.0e+00, 6.5e+00
 Total CPU time (secs)  = 0.09  
 CPU time per iteration = 0.01  
 termination code       =  0
 DIMACS: 6.9e-14  0.0e+00  1.7e-12  0.0e+00  5.3e-10  5.3e-10
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.337059
 
Done! 
The Chebyshev center coordinates are: 
   -0.1116
   -1.5760
    0.1079
   -2.1751
    3.2264
    3.5820
    4.3394
    3.0680
    0.4449
    0.3164

The radius of the largest Euclidean ball is: 
    0.3371

</pre>
</div>
</body>
</html>